package codetop.microsoft.T47;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-08-17 12:06:33 星期三
 */
class Solution {
    private List<List<Integer>> results = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, new ArrayList<>(), new boolean[nums.length]);
        return results;
    }

    private void dfs(int[] nums, List<Integer> res, boolean[] used) {
        if (res.size() == nums.length) {
            results.add(new ArrayList<>(res));
            return;
        }
        for (int i=0; i<nums.length; ++i) {
            if (!used[i]) {
                if (i > 0 && nums[i-1] == nums[i] && !used[i-1])
                    continue;
                used[i] = true;
                res.add(nums[i]);
                dfs(nums, res, used);
                res.remove(res.size()-1);
                used[i] = false;
            }
        }
    }
}